package com.shawn.leetcode.array.one;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.com/problems/majority-element/">majority-element</a>
 * <p>
 *	Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
 *
 *  You may assume that the array is non-empty and the majority element always exist in the array.
 *
 * Example 1:
 *
 * 	Input: [3,2,3]
 * 	Output: 3
 * 	Example 2:
 *
 * 	Input: [2,2,1,1,1,2,2]
 * 	Output: 2
 *
 * </p>
 *
 * @author com.shawn
 */
public class MajorityElement {

	/**
	 * HashTable
	 * @param nums
	 * @return
	 */
	public int majorityElement(int[] nums) {
		if(nums == null){
			return -1;
		}
		int n = nums.length;
		int result = 0;
		Map<Integer,Integer> map = new HashMap<>();
		for (int i = 0; i < n; i++) {
			int key = nums[i];
			Integer count = map.get(key);
			if(count == null){
				count = 1;
			}else{
				count ++;
			}
			map.put(nums[i], count);
			if(count > n / 2){
				result = nums[i];
				break;
			}
		}
		return result;
	}

}
